package cn.genmer.test.security.leetcode.medium;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 *  1705. 吃苹果的最大数目(中等)
 *
 *  有一棵特殊的苹果树，一连 n 天，每天都可以长出若干个苹果。在第 i 天，树上会长出 apples[i] 个苹果，这些苹果将会在 days[i] 天后（也就是说，第 i + days[i] 天时）腐烂，变得无法食用。也可能有那么几天，树上不会长出新的苹果，此时用 apples[i] == 0 且 days[i] == 0 表示。
 * 你打算每天 最多 吃一个苹果来保证营养均衡。注意，你可以在这 n 天之后继续吃苹果。
 * 给你两个长度为 n 的整数数组 days 和 apples ，返回你可以吃掉的苹果的最大数目。
 *
 * 示例 1：
 *
 * 输入：apples = [1,2,3,5,2], days = [3,2,1,4,2]
 * apples = [1,2,1,4,2]
 * 输出：7
 * 解释：你可以吃掉 7 个苹果：
 * - 第一天，你吃掉第一天长出来的苹果。
 * - 第二天，你吃掉一个第二天长出来的苹果。
 * - 第三天，你吃掉一个第二天长出来的苹果。过了这一天，第三天长出来的苹果就已经腐烂了。
 * - 第四天到第七天，你吃的都是第四天长出来的苹果。
 * 示例 2：
 *
 * 输入：apples = [3,0,0,0,0,2], days = [3,0,0,0,0,2]
 * 输出：5
 * 解释：你可以吃掉 5 个苹果：
 * - 第一天到第三天，你吃的都是第一天长出来的苹果。
 * - 第四天和第五天不吃苹果。
 * - 第六天和第七天，你吃的都是第六天长出来的苹果。
 *  
 *
 * 提示：
 * apples.length == n
 * days.length == n
 * 1 <= n <= 2 * 104
 * 0 <= apples[i], days[i] <= 2 * 104
 * 只有在 apples[i] = 0 时，days[i] = 0 才成立
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximum-number-of-eaten-apples
 */
public class MaxNumberEatingApple {
    public static void main(String[] args) {
        //
        System.out.println(eatenApples2(new int[]{2,1,10}, new int[]{2,10,1}));
//        System.out.println(eatenApples(new int[]{1,2,3,5,2}, new int[]{3,2,1,4,2}));
    }

    /**
     * 思路： 遍历，按顺序吃苹果，吃之前判断当前天数的苹果是否存在，以及是否过期，但是无法完成选择保质期最短的
     * @param apples
     * @param days
     * @return
     */
    public static int eatenApples(int[] apples, int[] days) {
        int canEatenDays = 0;
        boolean flag = true;
        int[] eatenApples = Arrays.copyOfRange(apples, 0, apples.length);
        // 0. 遍历apples，i是当前在吃第几天的苹果
        int i=0;
        while (i<apples.length){
            if (flag){
                eatenApples[i] = Math.min(apples[i], days[i]); // 0,1,3,5,2
                flag = false;
            }
            // 第i天的苹果还有且没过期
            if ((eatenApples[i] >0 && canEatenDays+1 <= i+days[i])){
                canEatenDays ++;
                eatenApples[i] = eatenApples[i]-1;
            } else {
                i++;
                flag = true;
            }
        }
        return canEatenDays;
    }

    /**
     * 贪心 + 优先队列（堆）
     * @param apples
     * @param days
     * @return
     */
    public static int eatenApples2(int[] apples, int[] days) {
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b)->a[0]-b[0]);
        int length = apples.length, time = 0, ans = 0;
        while (time < length || !q.isEmpty()) {
            if (time < length && apples[time] > 0)
                // 其中二元组表示 (最后食用日期, 当日产生苹果数量)(最后食用日期,当日产生苹果数量)，同时需要过滤 apples[time] = 0apples[time]=0 的情况。
                q.add(new int[]{time + days[time] - 1, apples[time]});
            // 遍历去除队列 时间最早的过期苹果
            while (!q.isEmpty() && q.peek()[0] < time) q.poll();
            if (!q.isEmpty()) {
                // 尝试从堆中取出「最后食用日期」最早「可食用」的苹果 cur，如果堆顶元素已过期，则抛弃；
                int[] cur = q.poll();
                // 如果吃掉 cur 一个苹果后，仍有剩余，并且最后时间大于当前时间（尚未过期），将 cur 重新入堆；
                // 为什么前面过滤了<time这里还要写，是在过滤 在当天过期的情况，当天过期，明天也就不能吃了
                if (--cur[1] > 0 && cur[0] > time) q.add(cur);
                ans++;
            }
            time++;
        }
        return ans;
    }
}
